package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC954 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean canReorderDoubled(int[] arr) {
            Map<Integer, Integer> mp = new TreeMap<>();
            for (int num : arr) {
                mp.put(num, mp.getOrDefault(num, 0) + 1);
            }

            while (mp.size() > 0) {
                int curKey = mp.keySet().iterator().next();
                if (curKey <= 0 && curKey % 2 != 0) return false;
                int nextKey = curKey <= 0 ? curKey / 2 : curKey * 2;
                if (!mp.containsKey(nextKey)) return false;
                if (mp.get(curKey).intValue() > mp.get(nextKey).intValue()) return false;
                if (mp.get(curKey).intValue() == mp.get(nextKey).intValue()) {
                    mp.remove(curKey);
                    mp.remove(nextKey);
                } else {
                    mp.put(nextKey, mp.get(nextKey) - mp.get(curKey));
                    mp.remove(curKey);
                }
            }

            return true;
        }
    }


    class Solution_Old {
        public boolean canReorderDoubled(int[] arr) {
            Arrays.sort(arr);
            Map<Integer, Integer> dict = new HashMap<>();
            for (int i = arr.length - 1; i >= 0; i--) {
                int target = arr[i] >= 0 ? arr[i] * 2 : arr[i] / 2;
                if (dict.containsKey(target)) {
                    if (dict.get(target).intValue() == 1) dict.remove(target);
                    else dict.put(target, dict.get(target) - 1);
                } else {
                    dict.put(arr[i], dict.getOrDefault(arr[i], 0) + 1);
                }
            }
            return dict.size() == 0;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,1,-8,8,-4,4,-4,2,-2]");
//        System.out.println(solution.canReorderDoubled(arr));
//        System.out.println(solution.canReorderDoubled(InputUtil.toIntegerArray("[3,1,3,6]")));
//        System.out.println(solution.canReorderDoubled(InputUtil.toIntegerArray("[4,-2,2,-4]")));
        System.out.println(solution.canReorderDoubled(InputUtil.toIntegerArray("[-5,-2]")));
    }

    public static void main(String[] args) throws Exception {
        LC954 an = new LC954();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
